#include <iostream>
#include <vector>

using namespace std;

class Solution1 {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        if (citations[n - 1] == 0)
            return 0;

        while (left < right)
        {
            int mid = (right - left) / 2 + left;

            if (citations[mid] >= n - mid)
                right = mid;
            else
                left = mid + 1;
        }

        return n - right;
    }
};

//////////////////////////////////////////////

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution2 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path_great, path_less;
        _lowestCommonAncestor(root, p, path_great);
        _lowestCommonAncestor(root, q, path_less);

        if (path_great.size() < path_less.size())
        {
            vector<TreeNode*> tmp = path_great;
            path_great = path_less;
            path_less = tmp;
        }
        int great = path_great.size() - 1, less = path_less.size() - 1;
        while (great != less)
        {
            great--;
        }

        while (path_great[great] != path_less[less])
        {
            great--;
            less--;
        }
        return path_great[great];
    }

    bool _lowestCommonAncestor(TreeNode* root, TreeNode* target, vector<TreeNode*>& path)
    {
        if (root == nullptr)
            return false;

        path.push_back(root);
        if (root == target)
            return true;
        if (_lowestCommonAncestor(root->left, target, path))
            return true;
        if (_lowestCommonAncestor(root->right, target, path))
            return true;

        path.pop_back();
        return false;
    }
};

//int main()
//{
//    TreeNode* node1 = new TreeNode(3);
//    TreeNode* node2 = new TreeNode(5);
//    TreeNode* node3 = new TreeNode(1);
//    TreeNode* node4 = new TreeNode(6);
//    TreeNode* node5 = new TreeNode(2);
//    TreeNode* node6 = new TreeNode(0);
//    TreeNode* node7 = new TreeNode(8);
//    TreeNode* node8 = new TreeNode(7);
//    TreeNode* node9 = new TreeNode(4);
//    node1->left = node2;
//    node1->right = node3;
//    node2->left = node4;
//    node2->right = node5;
//    node3->left = node6;
//    node3->right = node7;
//    node5->left = node8;
//    node5->right = node9;
//
//    Solution().lowestCommonAncestor(node1, node2, node9);
//    return 0;
//}

/////////////////////////////

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
        if (pRootOfTree == nullptr)
            return prev;
        _Convert(pRootOfTree, prev, pRootOfTree);

        prev = pRootOfTree;
        while (prev->left)
        {
            prev = prev->left;
        }
        return prev;
    }

    void _Convert(TreeNode* cur, TreeNode*& prev, TreeNode*& root)
    {
        if (cur == nullptr)
            return;

        _Convert(cur->left, prev, root);
        if (prev != nullptr)
        {
            cur->left = prev;
            prev->right = cur;
        }
        prev = cur;
        _Convert(cur->right, prev, root);
    }
};

int main()
{
    TreeNode* node1 = new TreeNode(10);
    TreeNode* node2 = new TreeNode(6);
    TreeNode* node3 = new TreeNode(14);
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(8);
    TreeNode* node6 = new TreeNode(12);
    TreeNode* node7 = new TreeNode(16);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;

    Solution().Convert(node1);

    return 0;
}